/**
 * 面试题 02.05. 链表求和
 * https://leetcode-cn.com/problems/sum-lists-lcci/
 */
public class Solutions_mianshi_02_05 {
    public static void main(String[] args) {
        int[] arr1 = {7, 1, 6};
//        int[] arr2 = {5, 9, 2};  // output: {2, 1, 9} = 912
        int[] arr2 = {5, 9};  // output: {2, 1, 7} = 712
        ListNode l1 = MyLinkedListUtils.ArrayToListNode(arr1);
        ListNode l2 = MyLinkedListUtils.ArrayToListNode(arr2);

        ListNode result = addTwoNumbers(l1, l2);
        System.out.println(MyLinkedListUtils.ListNodeToString(result));
    }

    /**
     * 解法二：迭代运算优化版（2ms）
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        int sum;
        while (l1 != null && l2 != null) {
            sum = l1.val + l2.val;
            l1 = l1.next;
            l2 = l2.next;
            // 和大于 10 时，需要进位 1，进位则涉及到链表的下一结点，若下一结点为空时，进行创建节点的操作
            if (sum >= 10) {
                // 两个个位数相加，最多进位 1
                // 哪个链表为 null，就创建一个值为 1 的结点，继续计算
                if (l1 == null) {
                    l1 = new ListNode(1);
                } else if (l2 == null) {
                    l2 = new ListNode(1);
                } else {
                    l1.val += 1;
                }
                sum %= 10;
            }
            cur.next = new ListNode(sum);
            cur = cur.next;
        }
        // 拼接上未遍历完的链表
        cur.next = l1 == null ? l2 : l1;
        return res.next;
    }

    /**
     * 解法一：迭代运算（3ms）
     */
    public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        int carry = 0;
        while (l1 != null || l2 != null || carry > 0) {
            if (l1 != null) {
                carry += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                carry += l2.val;
                l2 = l2.next;
            }
            // 取余数
            cur.next = new ListNode(carry % 10);
            cur = cur.next;
            // 进位（两个个位数相加，最多进位 1）
            carry = carry / 10;
        }
        return res.next;
    }
}
